/*-
 * Copyright 2012 Guram Dukashvili
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
//---------------------------------------------------------------------------
#include "sys.h"
#include "vector.h"
//---------------------------------------------------------------------------
static void vector_pointer_init(void * p)
{
  *(void **) p = NULL;
}
//---------------------------------------------------------------------------
vector * vector_new()
{
  vector * v = salloc(sizeof(vector),NULL);
  if( v != NULL )
    vector_init(v);
  return v;
}
//---------------------------------------------------------------------------
void vector_init(vector * v)
{
  array_init(&v->pointers);
  v->pointers.element_init = vector_pointer_init;
  array_set_element_size(&v->pointers,sizeof(void *),sizeof(void *) * 8);
  v->element_new = NULL;
  v->element_delete = NULL;
  v->element_copy = NULL;
  v->element_compare = NULL;
  v->element_size = 0;
}
//---------------------------------------------------------------------------
void vector_destroy(vector * v)
{
  if( v->element_delete != NULL ){
    uintptr_t i = v->pointers.count;
    void ** p = (void **) v->pointers.a + i;
    while( i-- > 0 ) v->element_deletef(*(--p),v->pointers.object);
  }

  array_destroy(&v->pointers);
}
//---------------------------------------------------------------------------
void vector_delete(vector * v)
{
  vector_destroy(v);
  sfree(v);
}
//---------------------------------------------------------------------------
void vector_copy(vector * v,const vector * src)
{
  vector_resize(v,src->pointers.count);

  if( errno == 0 ){

    uintptr_t i, e = v->pointers.count;
    void ** p = (void **) v->pointers.a, ** a = (void **) src->pointers.a;

    if( v->element_copy != NULL ){

      for( i = 0; i < e; i++, p++, a++ )
        v->element_copyf(p,a,v->pointers.object);
    }
    else {
#if COMPILE_RUNTIME_CHECKS
      if( v->element_size != src->element_size ){
        fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
        abort();
      }
#endif
      for( i = 0; i < e; i++, p++, a++ )
        memcpy(*p,*a,v->element_size);
    }

  }
}
//---------------------------------------------------------------------------
void vector_resize(vector * v,uintptr_t n)
{
  uintptr_t i, c = v->pointers.count;
  void ** p = (void **) v->pointers.a + c;

  if( v->element_delete != NULL ){
    for( i = c; i > n; i-- )
      v->element_deletef(*(--p),v->pointers.object);
  }
  else {
    for( i = c; i > n; i-- )
      sfree(*(--p));
  }

  array_resize(&v->pointers,n);

  if( errno == 0 ){

    p = (void **) v->pointers.a + c;

    if( v->element_new != NULL ){
      for( i = c; i < n; i++, p++ )
        if( (*p = v->element_newf(v->pointers.object)) == NULL ) break;
    }
    else {
      for( i = c; i < n; i++, p++ )
        if( (*p = salloc(v->element_size,NULL)) == NULL ) break;
    }
  }
}
//---------------------------------------------------------------------------
void vector_append(vector * v)
{
  void * p = v->element_new != NULL
    ? v->element_newf(v->pointers.object)
    : salloc(v->element_size,NULL);

  if( p != NULL ){

    array_append_copy(&v->pointers,&p);

    if( errno != 0 ){
      int err = errno;

      if( v->element_delete != NULL )
        v->element_deletef(p,v->pointers.object);
      else
        sfree(p);

      errno = err;
    }
  }
}
//---------------------------------------------------------------------------
void vector_append_ptr(vector * v,const void * data)
{
  array_append_copy(&v->pointers,&data);
}
//---------------------------------------------------------------------------
void vector_insert(vector * v,uintptr_t idx)
{
  void * p = v->element_new != NULL
    ? v->element_newf(v->pointers.object)
    : salloc(v->element_size,NULL);

  if( p != NULL )
    array_insert_copy(&v->pointers,idx,&p);
}
//---------------------------------------------------------------------------
void vector_insert_ptr(vector * v,uintptr_t idx,const void * data)
{
  array_insert_copy(&v->pointers,idx,&data);
}
//---------------------------------------------------------------------------
void vector_remove(vector * v,uintptr_t idx)
{
  void ** p = (void **) v->pointers.a + idx;
#if COMPILE_RUNTIME_CHECKS
  if( idx >= v->pointers.count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif

  if( v->element_delete != NULL )
    v->element_deletef(*p,v->pointers.object);
  else
    sfree(*p);

  *p = NULL;

  array_remove(&v->pointers,idx);
}
//---------------------------------------------------------------------------
void vector_xchg_elements(vector * v,uintptr_t idx,uintptr_t new_idx)
{
  void ** p1 = (void **) v->pointers.a + idx;
  void ** p2 = (void **) v->pointers.a + new_idx;
  void * p = *p1;
#if COMPILE_RUNTIME_CHECKS
  if( idx >= v->pointers.count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
  if( new_idx >= v->pointers.count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif
  *p1 = *p2;
  *p2 = p;
}
//---------------------------------------------------------------------------
void vector_copy_paste(
  vector * v,
  uintptr_t dst_position,
  const vector * src,
  uintptr_t src_position,
  uintptr_t count)
{
#if COMPILE_RUNTIME_CHECKS
  if( dst_position > v->pointers.count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
  if( src_position >= src->pointers.count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
  if( src_position + count > src->pointers.count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif

  array_resize(&v->pointers,v->pointers.count + count);

  if( errno == 0 ){

    uintptr_t i;
    void ** p = (void **) v->pointers.a + dst_position;

    memmove(p + count,p,count * sizeof(void *));

    for( i = 0; i < count; i++ ) p[i] = NULL;

    errno = 0;

    if( v->element_new != NULL ){
      for( i = 0; i < count; i++ )
        if( (p[i] = v->element_newf(v->pointers.object)) == NULL ) break;
    }
    else {
      for( i = 0; i < count; i++ )
        if( (p[i] = salloc(v->element_size,NULL)) == NULL ) break;
    }

    if( errno == 0 ){

      if( v->element_copy != NULL ){
        for( i = 0; i < count; i++ )
          v->element_copyf(p[i],*((void **) src->pointers.a + src_position),v->pointers.object);
      }
      else {
#if COMPILE_RUNTIME_CHECKS
        if( v->element_size != src->element_size ){
          fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
          abort();
        }
#endif
        for( i = 0; i < count; i++ )
          memcpy(p[i],*((void **) src->pointers.a + src_position),v->element_size);
      }
    }
  }
}
//---------------------------------------------------------------------------
intptr_t vector_lookup(const vector * v,const void * data,uintptr_t * insert_position)
{
  intptr_t low = 0, high = v->pointers.count - 1, pos, c;

  *insert_position = 0;

  if( v->element_compare != NULL )

    for(;;){

      pos = (low + high) / 2;

      if( low > high ) break;

      c = v->element_comparef(data,*((void **) v->pointers.a + pos),v->pointers.object);

      if( c > 0 ){
        *insert_position = low = pos + 1;
      }
      else if( c < 0 ){
        high = (*insert_position = pos) - 1;
      }
      else
        return pos;
    }

  else

    for(;;){

      pos = (low + high) / 2;

      if( low > high ) break;

      c = memcmp(data,*((void **) v->pointers.a + pos),v->element_size);

      if( c > 0 ){
        *insert_position = low = pos + 1;
      }
      else if( c < 0 ){
        high = (*insert_position = pos) - 1;
      }
      else
        return pos;
    }
  return -1;
}
//---------------------------------------------------------------------------
intptr_t vector_lookup_ptr(const vector * v,const void * ptr)
{
  void ** pp1 = (void **) v->pointers.a;
  void ** pp2 = (void **) v->pointers.a + v->pointers.count;

  while( pp1 < pp2 ){
    if( ptr == *pp1 ) return pp1 - (void **) v->pointers.a;
    pp1++;
  }
  return -1;
}
//---------------------------------------------------------------------------
static __inline__ intptr_t compare(const vector * v,intptr_t p1,intptr_t p2)
{
  void ** pp1 = (void **) v->pointers.a + p1;
  void ** pp2 = (void **) v->pointers.a + p2;
  return v->element_compare != NULL
    ? v->element_comparef(*pp1,*pp2,v->pointers.object)
    : memcmp(*pp1,*pp2,v->element_size);
}
//---------------------------------------------------------------------------
static __inline__ void xchg(const vector * v,intptr_t x1,intptr_t x2)
{
  void ** px1 = (void **) v->pointers.a + x1;
  void ** px2 = (void **) v->pointers.a + x2;
  void * x = *px1;
  *px1 = *px2;
  *px2 = x;
}
//---------------------------------------------------------------------------
static void my_qsort(const vector * v,intptr_t lb,intptr_t ub)
{
  intptr_t l, r, m;

  if( lb < ub ){

    if( ub - lb < 12 ){

      for( r = ub; r > lb; r-- ){

        for( m = r, l = m - 1; l >= lb; l-- )
          if( compare(v,m,l) < 0 ) m = l;

        xchg(v,m,r);
      }

    }
    else {

      m = lb + ((ub - lb) >> 1);
      l = lb, r = ub;

      for(;;){

        while( l < r && compare(v,m,l) > 0 ) l++;

        while( r >= l && compare(v,m,r) < 0 ) r--;

        if( l >= r ) break;

        xchg(v,l,r);

        if( r == m ) m = l;
        else if( l == m ) m = r;

        l++;
        r--;
      }

      my_qsort(v,lb,r);
      my_qsort(v,r + 1,ub);

    }
  }
}
//---------------------------------------------------------------------------
void vector_sort(vector * v)
{
  my_qsort(v,0,v->pointers.count - 1);
}
//---------------------------------------------------------------------------
